// Created by WXX on 2021/12/14 21:48
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：28 ms, 在所有 C++ 提交中击败了40.54%的用户
 * 内存消耗：24.2 MB, 在所有 C++ 提交中击败了32.43%的用户
 */
// 写法一
//class Solution {
//public:
//    vector<int> prevPermOpt1(vector<int>& arr) {
//        int k = arr.size() - 1;
//        while (k > 0 && arr[k - 1] <= arr[k]) k--;
//        if (k == 0) {  // 说明是最小值
//            return arr;
//        } else {
//            int t = k;
//            while (t < arr.size() && arr[t] < arr[k - 1]) t++;
//            while (arr[t - 2] == arr[t - 1]) t--;
//            swap(arr[k - 1], arr[t - 1]);
//        }
//        return arr;
//    }
//};

// 写法二
class Solution {
public:
    vector<int> prevPermOpt1(vector<int>& arr) {
        int k = arr.size() - 2;
        while (k >= 0 && arr[k] <= arr[k + 1]) k--;
        if (k < 0) {  // 说明是最小值
            return arr;
        } else {
            int t = k + 1;
            while (t + 1 < arr.size() && arr[t + 1] < arr[k]) t++;
            while (arr[t - 1] == arr[t]) t--;
            swap(arr[k], arr[t]);
        }
        return arr;
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<int> arr = {3, 2, 1};
    OutputBasicArray1D(Solution().prevPermOpt1(arr));

    return 0;
}
